package array;

/**
 * @Author quan
 * @Description LeetCode_Num704: 二分查找
 * @Date 2023/4/23 21:45
 */
public class Demo1_binarySearch {
    /*
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
     * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     * 输入: nums = [-1,0,3,5,9,12], target = 9
     * 输出: 4
     * 解释: 9 出现在 nums 中并且下标为 4
     */

    /*
     * 最直接的解法
     */
//    public int search(int[] nums, int target) {
//        //遍历数组，判断target是否存在，存在的话返回所在数组中的索引下标即可。
//        for (int i = 0; i < nums.length; i++) {
//            if(nums[i] == target){
//                return i;
//            }
//        }
//        return -1;
//    }
    /**
     * 二分法1：注意两种方式的middle的取值
     * 定义 target 是在一个在左闭右闭的区间里，也就是[left, right]
     */
//    public int search(int[] nums, int target) {
//        int left = 0;
//        int right =nums.length-1;
//        while (left<=right){
//            int middle = left+((right-left)/2);//防止数据溢出
//            // 当查找的元素在数组左半部分，更新right为middle-1
//            if(nums[middle] > target){
//                right = middle-1;
//            }
//            //如果查找的元素在数组右半部分，更新left为middle+1
//            if (nums[middle] < target) {
//                left = middle+1;
//            }
//            //直到中间元素是待查找的目标值
//            if(nums[middle] == target) {
//                return middle;
//            }
//        }
//        //循环结束还没找到，说明该元素值不存在
//        return -1;
//    }
    /**
     * 二分法2：定义区间为左闭右开
     */
    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length;//right是开区间取不到，所以索引可以是数组长度
        while (left < right){
            int middle = left+((right-left)/2);
            if(nums[middle] > target){
                right = middle;//因为right是开区间，middle不可能是target
            }
            if(nums[middle] < target){
                left = middle +1;//left是闭区间，所以要加1
            }
            if(nums[middle] == target){
                return middle;
            }
        }
        return -1;
    }
}
